package org.example.algorithm.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//N皇后问题
public class SolveNQueensSolution {

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();
        int[] queen = new int[n];
        boolean[] col = new boolean[n];
        boolean[] range1 = new boolean[2*n-1];
        boolean[] range2 = new boolean[2*n-1];
        dfs(0, ans, queen, col, range1, range2);
        return ans;
    }

    private void dfs(int row, List<List<String>> ans, int[] queen, boolean[] col, boolean[] range1, boolean[] range2) {
        int n = col.length;
        if (row == n) {
            //生成一个答案
            List<String> list = new ArrayList<>();
            for (int queenCol: queen) {
                char[] item =  new char[n];
                Arrays.fill(item, '.');
                item[queenCol] = 'Q';
                String rowAns = new String(item);
                list.add(rowAns);
            }
            ans.add(list);
            return;
        }
        for (int j=0;j<n;j++) {
            int attack = row - j + n - 1;
            if (!col[j] && !range1[row+j] && !range2[attack]) {
                queen[row] = j;
                col[j] = range1[row+j] = range2[attack] = true;
                dfs(row+1, ans, queen, col, range1, range2);
                col[j] = range1[row+j] = range2[attack] = false;
            }
        }
    }
}
